// 写得非常好
#include <bits/stdc++.h>
using namespace std;
const int N = 500500;
int pre[N], suf[N];
void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  s = " " + s;

  pre[0] = suf[n + 1] = 0;

  for (int i = 1; i <= n; i++) {
    if (s[i] == '1')
      pre[i] = pre[i - 1] + 1; // 前缀和：前i个字符中'1'的个数
    else
      pre[i] = pre[i - 1];
  }

  for (int i = n; i >= 1; i--) {
    if (s[i] == '1')
      suf[i] = suf[i + 1] + 1; // 后缀和：从i到n的字符中'1'的个数
    else
      suf[i] = suf[i + 1];
  }

  int ans = 1e9;
  if (pre[n] == 0 || pre[n] == n) {
    ans = 0;
  }

  int i = 1;
  while (i <= n) {
    int j = i;
    int cnt = 1;
    while (j + 1 <= n && s[j + 1] == s[j]) {
      j++;
    }
    int cnt1 = pre[i - 1] + suf[j + 1];
    int cnt0 = (i - 1 - pre[i - 1]) + (n - j - suf[j + 1]);
    if (s[j] == '1') {
      ans = min(ans, cnt1 * 2 + cnt0); // 转化成全1的代价
    } else {
      ans = min(ans, cnt0 * 2 + cnt1); // 转化成全0的代价
    }
    i = j + 1;
  }

  //张旻煊的好思路： 可以找到最长的连续0区域（ 假如目标是变成全0）
  //可以找到最长的连续1区域（ 假如目标是变成全1）
  cout << ans << endl;
}

int main() {

  int T;
  cin >> T;
  while (T--) {
    solve();
  }
}